package datastructure.sort;

/**
 * @author MaoLin Wang
 * @date 2020/10/7 6:03 下午
 */
public class QuickSort2 {

    public static void quickSort(int[] addr) {
        if (addr.length<=1){
            return;
        }
        quickSort(addr,0,addr.length-1);
    }

    private static void quickSort(int[] addr, int left, int right) {
        if (left>=right){
            return;
        }
        int  mid=sort(addr,left,right);
        quickSort(addr,left,mid-1);
        quickSort(addr,mid+1,right);
    }

    private static int sort(int[] addr, int left, int right) {
        int pivot=addr[left];
        int l=left;
        int r=right+1;
        while (true){
            while (addr[++l]<pivot){
                if (l>r){
                    break;
                }
            }
            while (addr[--r]>pivot){
                if (r<l){
                    break;
                }
            }
            if (l>=r){
                break;
            }
            swap(addr,l,r);
        }
        swap(addr,left,r);
        return r;
    }

    private static void swap(int[] addr, int l, int r) {
        int temp=addr[l];
        addr[l]=addr[r];
        addr[r]=temp;
    }

    public static void main(String[] args) {
        int[]ints=new int[]{21,4,436,8,90,3,2,43,2,3};
        quickSort(ints);
        for (int i : ints) {
            System.out.println(i);
        }

    }
}
